Chapter 1 Sentential Logic

#mathematical_logic #sentential_logic

本文写于 2025.10.11。

语句逻辑是一门语言。它的核心在于用参数符号表示声明语句（atomic declarative sentence），将其作为原子并用特定的逻辑符号来联系它们以构成表达式。不同于自然语言，我们只关注表达式的正确性。当所有参数符号的正确性都给定时，任何使用这些参数符号的表达式的正确性都可以被确定。语句逻辑创立的初衷就是为了让命题的正确性完全决定于推理形式的正确性（在前提真的情况下），从而一切命题的正确性都可以通过计算得到。

• 当然，前提是提供了恰当的结构构建（通常在翻译自然语言为语句逻辑语言时），譬如 $p:x=1,q:y=1,r:x=y=1$ 显然 $r=p\wedge q$ 但是这不构成有效的推理形式。
• 不过，很不幸，语句逻辑并没有完成它的使命。它的的表达方式存在相当的局限性，用单一的符号来表示命题的表达能力十分有限，并不能反应命题之间细微的结构关系。从而导致并不是所有自然语言的有效推理形式在语句逻辑中都有对应的有效推理形式。如 $p:x=1,q:y=2,r:x+y=3$ 在自然语言意义下成立的 $p\wedge q\to r$ 在语句逻辑中并不构成有效的推理形式。

构建语句逻辑语言的第一步是设定符号集合（就像确定中文里的汉字）并规定这些符号形成 Well-Formed Formula 的规则（确定汉语中的句法、词法规则），第二步是确定通过参数符号的正确性 导出 wff 表达式的正确性的规则（指定汉字、词语符号的含义以及它们如何形成句子的含义的规则。此时语句便有了意义，进而可以组句成章，文章对应从语句逻辑语言构成的证明）。

• 逻辑符号 $\mathrm{\neg }\vee \wedge \to \leftrightarrow ()$
• 语句符号（或称之为参数） $A_1{A}_2{A}_3\cdots$。这里采用了可数个参数，是否可以拓展为不可数集？若限定有限符号集可将 $A_n$ 以 $A^{″\cdots }$ 代替。语句符号集合包含无限个语句符号而不是有限个可以以日常生活中使用到的汉字仅是全部汉字符号中的一部分来类比。

目前这些符号都不具有实际意义。实际上符号只是用来指代实体，只有确定了对应的实体之后符号才有意义。符号的选择可以是任意的，逻辑符号被选择以这样的符号表示的原因只有当其被赋予了它固定的意义之后才会彰显，也就是符号象形意义到实体意义的直观性。

符号的选择必须保证任意符号不是任何其他符号可以组成的有限序列。这确保了符号序列分解的唯一性。

表达式定义为符号的有限序列。我们为表达式规定 concatenating operation，表达式 $AB$ 意味着由 $A$ $B$ 的符号依次连接形成的新表达式，不难定义其多元形式，并且由于显然的结合性，多元形式可以任意规定组合顺序。

我们可以定义从自然语言符号序列到表达式的映射（？）（需要选定自然语言符号序列的原子部分并规定其到语句符号的映射关系），这样的映射将会筛选出这样的语句中我们关心的性质。

自然语言符号序列不一定是合规的自然语言语句，同样表达式不一定是 Well-Formed-Formula（mathematically corret expression）。只有当将语句逻辑作为一门语言并从还未被赋予意义的底层符号结合规律来开始构建它，定义 wff 才是有意义的，如果一开始为符号赋予了意义并且完全没有强调符号之于意义的独立性（比如石书），那么符号之间的结合规律都是显然的。

定义 expression 的 formula-building operation function，$◻=\mathrm{\neg },\wedge ,\vee ,\to ,\leftrightarrow$

• one-place ${\mathcal{E}}_{◻}(A)=(◻A)$
• two-place ${\mathcal{E}}_{◻}(A,B)=(A◻B)$

wff definition:

• sentence symbols are wffs
• if $\alpha ,\beta$ are wffs, then ${\mathcal{E}}_{\mathrm{\neg }}(\alpha ),{\mathcal{E}}_{\vee }(\alpha ,\beta ),{\mathcal{E}}_{\wedge }(\alpha ,\beta ),{\mathcal{E}}_{\to }(\alpha ,\beta ),{\mathcal{E}}_{\leftrightarrow }(\alpha ,\beta )$ are wffs
• any expressions else are not wffs

这是一个 Induction 的定义

wff 的定义是一个间接的构造定义吗？可以有两种构造的理解：

• 从仅包含 sentence symbols 的 wffs 集合 $WFF$ 开始，按照第二条规则不断扩充。
• 测试表达式全集 $U$，将满足前两条的加入当前 wffs 集合 $WFF$。

实际上，该定义在另一个方向上的叙述也是正确的，即任意 wffs 的包含 sentence symbols 并在 formula-building oepration 下封闭的子集必定是 wffs 全集

可以通过直观的 ancestral tree 或者 construction sequence 简单地 informal 地证明

Truth Assignment

Truth Assignment 是一个映射 $v:\mathcal{S}\to \{F,T\}$，其中 $\mathcal{S}$ 是 sentence symbol 集合。定义了 $v$ 就意味着我们考虑的不是多值逻辑而是布尔逻辑。

设 $\overline{\mathcal{S}}$ 是 $\mathcal{S}$ 构建的 wff 集合，则可以构建这样一个 $\overline{v}:\overline{\mathcal{S}}\to \{F,T\}$ ，它可以由如下性质唯一确定

• $\mathrm{\forall }A\in S,\overline{v}(A)=v(A)$
• $\overline{v}((\mathrm{\neg }\alpha ))=\cdots$
• $\overline{v}((\alpha \wedge \beta ))=\cdots$
• $\cdots$

一些定义：

• truth assignment $v$ satisfy wff $\varphi$ iff $\overline{v}(\varphi )=T$
• a set of wffs $\mathrm{\Sigma }$ tautologically implies a wff $\tau$ (written $\mathrm{\Sigma }\models \tau$) iff every truth assignment of sentence symbols in $\mathrm{\Sigma }$ and $\tau$ that satisfies every member of $\mathrm{\Sigma }$ also satisfy $\tau$. Specially when $\mathrm{\Sigma }=\varnothing$ $\tau$ is called tautology(written $\models \tau$), and when no truth assignment satisfy every member of $\mathrm{\Sigma }$, it is vacuously true that $\mathrm{\Sigma }\models \tau$.

Truth Table

trick to simplify calculation

A Selected List of Tautologies

A Parsing Algorithm

polish notation
omitting parentheses

Induction

和 Recursion 一起，是本章最有趣的部分

假设这样一个情形，全集 $U$，给定函数集合 $\mathcal{F}$，其中所有函数都形如 $f:U^k\to U,k=1,2,3,\cdots$，以及初始集合 $B$，集合 $C$ 初始为 $B$，我们反复取出 $C$ 中的若干元素，应用 $\mathcal{F}$ 中的函数并将得到的新元素添加至 $C$ 直到无法得到新的元素。

这样的 $C$ 在直觉上是包含 $B$ 且对 $\mathcal{F}$ 中任意函数封闭的 $U$ 的最小子集，且它是存在且唯一的。现在我们需要为这样的 $C$ 给出一个严谨的定义。

封闭定义为：集合 $S\subseteq U$ 对 $f:U^k\to U$ 封闭当且仅当任意 $e_1,e_2,\cdots ,e_k\in S$ 都有 $f(e_1,e_2,\cdots ,e_3)\in S$ 。我们注意到封闭性在集合的交集操作下是保持的，即 $S_1,S_2$ 对 $f$ 封闭，意味着 $S_1\cap S_2$ 仍对 $f$ 封闭。

第一种定义：定义 inductive set 为 $U$ 的子集 $S$，满足 $B\subseteq S$ 且 $S$ 对 $\mathcal{F}$ 中的任意函数封闭，定义 $C^{\star }$ 为 $U$ 的所有 inductive set 的交集（刻画最小性）。由于封闭性和包含性在集合的交集操作下是保持的，自然 $C^{\star }$ 也满足 $B\subset C^{\star }$ 且对任意 $\mathcal{F}$ 中的函数封闭。

第二种定义：定义 construction sequence 为一列表达式 $⟨s_1,s_2,\cdots ,s_k⟩$ 满足：对于任意 $s_i$，或 $s_i\in B$，或 $\mathrm{\exists }f\in \mathcal{F},t_1,t_2,\cdots ,t_k<i$ 满足 $f(s_{t_1},s_{t_2},\cdots ,s_{t_k})=s_i$。$C_{\star }$ 定义为包含所有这样的 $x$ 的集合：存在以 $x$ 结尾的 construction sequence。这定义依赖于自然数的定义。

这两种定义是等价的，证明略。所以统称为 $C=C^{\star }=C_{\star }$，并称 $C$ 是 $B$ 经过 $\mathcal{F}$ 所生成的集合。

$C$ 的最小性是一个重要的性质，被称为 Induction Principle

$\text{Induction Principle}$：若集合 $C$ 是由集合 $B$ 经 $\mathcal{F}$ 所生成的，那么任意 $C$ 的子集 $S$，满足 $B\subseteq S$ 且 $S$ 对 $\mathcal{F}$ 中任意函数封闭，就有 $S=C$

其正确性在于 $S$ 是 inductive set，从而 $C\subseteq S$。

利用 Induction Principle 我们可以立即（从集合论的角度，否则涉及循环论证）得到数学归纳法的正确性。数学归纳法说的是在论域 $\mathbb{N}$ 上 $P(1)\wedge \mathrm{\forall }n(>n1)\to (P(n-1)\to P(n))\leftrightarrow \mathrm{\forall }nP(n)$ 为重言式。$C=\mathbb{N}$ 是由 $B=\left\{1\right\}$ 经 $f(x)=x+1$ 所生成的，令 $S=\{n|P(n)\}$，如果 $P(1)$ 即 $B=\left\{1\right\}\subseteq S$，且 $P(n-1)\Rightarrow P(n)$ 即 $S$ 对 $f$ 封闭，那么 $S=C=\mathbb{N}$。

Recursion

假设我们要在如上的 $C$ 上递归地定义一个映射 $h:U\to V$（根据 $C$ 的结构，递归地定义是自然的），即通过

1. 给定 $h$ 在 $B$ 上的映射关系
2. $\mathrm{\forall }f\in \mathcal{F}$ 给定 $H_f:V^k\to V$，以此来描述 $h(f(\cdots ))$ 如何通过 $h(\cdots )$ 计算得到，即 $h(f(s_1,s_2,\cdots ,s_k))=H_f(h(s_1),h(s_2),\cdots ,h(s_k))$

来唯一地确定一个映射 $h$。但这样的 $h$ 并不总是存在的，我们有如下的 Recursion Theorem 阐明了判定 $h$ 唯一存在的一个充分条件

自由生成（freely-generated）可以用来描述生成的结构是否“清晰”，即每个生成的元素的"生成序列"（按顺序施加的函数序列）是否可以被唯一确定，其定义为：$C$ 是 $B$ 经 $\mathcal{F}$ 自由生成的，当且仅当 $C$ 是由 $B$ 经 $\mathcal{F}$ 生成的，并且

• $\mathcal{F}$ 中的映射在 $C$ 上是一一映射。
• $\mathcal{F}$ 中映射的在 $C$ 上的值域以及 $B$，两两不相交。

$\text{Recusion Theorem}$：如果 $C$ 是由 $B$ 经 $\mathcal{F}$ 生成的，那么满足 1. 和 2. 的 $h$ 唯一存在当 $C$ 由 $B$ 经 $\mathcal{F}$ 自由生成。

我们非形式化地进一步叙述：$h$ 不存在当且仅当 $\mathcal{F}$ 中映射的值域存在相交且对应相交的两个映射在任意值域交集中的一点的所有对应可能的自变量都在给定的 $H$ 中使 $h$ 被映射到了不同的值。

不必要是因为 $h$ 的唯一性并不等价于"生成序列"的唯一性，$h$ 的映射关系可以按照“生成序列”迭代计算得到，某一步出现多种路径并不必然导致最终结果不同。一个反例：$B=\left\{a\right\}$，$\mathcal{F}$ 仅包含一个恒等映射 $id$，从而 $C=\left\{a\right\}$，定义 $h(a)=1$ 以及 $H_{id}=id$，从而 $h(a)$ 不止一条"生成路径"：直接通过 $B$ 或者经过若干次恒等映射。

Unique Readability Theorem 作为其直接推论断言了 $\overline{v}$ 的存在性和唯一性

Sentential Connectives

本章建立了 Boolean Function 与 wff 之间的一一映射，并将常见的 wff 语言翻译为函数的语言

$\overline{v}(\alpha )$ 描述的是给定一组 truth assignment $v$ 时 wff 到 $\{F,T\}$ 的映射关系
$B_{\alpha }(\overrightarrow{X})$ 描述的是给定一个 wff $\alpha$（其涉及 $n$ 个 sentence symbol $s_1,s_2,\cdots ,s_n$）时 truth assignment $\overrightarrow{X}=(v(s_1),v(s_2),\cdots ,v(s_n))$ 到 $\{F,T\}$ 的映射关系。它可以由 wff 唯一确定（定义）。另一方面从 $B$ 也可以唯一地构造一个 wff。

• $\alpha \models \beta$ 等价于任意 $\overrightarrow{X}\in {\{F,T\}}^n$ 都有 $B_{\alpha }(\overrightarrow{X})\le B_{\beta }(\overrightarrow{X})$
• $\alpha \models \beta$ 且 $\beta \models \alpha$ 等价于 $B_{\alpha }=B_{\beta }$
• $\models \alpha$ 等价于 $B_{\alpha }$ 是常值 $T$ 函数

以下的讨论内容过于平凡，均可以简单地在布尔函数范围内得到答案

• distinctive/conjunctive normal form
• complete sentential connectives set

Compactness

Effectiveness

Comments

本章似乎并没有介绍逻辑推演（仅给出了通过真值表/布尔函数的判定方法），即通过 wff 的变换（称为推理规则，如假言推理。这是一种基于语法分析而非语义分析的方法。虽然推理规则的规定基于语义，但是一旦规定了完备的推理规则，便可以依赖于纯粹的语法分析）来简化（复杂度较枚举真值下降）、直观化逻辑蕴含的判定问题。观察目录疑似在一阶逻辑章节一并叙述。

在撰写本文时，并没有区分命题逻辑和语句逻辑这两个概念。不过实际上，二者仅有细微地差别，命题逻辑认为原子命题是一个可以确定真假的陈述句，这一点在构成表达式之前就需要确定，侧重语义方面；而语句逻辑并没有为句子符号规定强制的含义，而是重在描述如何用句子符号构成表达式，只需要在 truth assignment 时为每一个句子符号分配一个真值即可，侧重语法方面。如 $x=2$ 不是一个命题，无法用（严谨地）命题逻辑以其为原子命题撰写表达式，延后 $x$ 的赋值。